package a09_贪心算法;

import java.util.Arrays;

/**
 * <p>
 * a18_无重叠区间复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/2/25
 */
public class a18_无重叠区间复习2 {

    public static void main(String[] args) {
        a18_无重叠区间复习2 test = new a18_无重叠区间复习2();
        System.out.println(test.eraseOverlapIntervals(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 3}}));
    }

    //[[1,2],[2,3],[3,4],[1,3]]
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (item1,item2) -> {
            if(item1[0] == item2[0]){
                if(item1[1] > item2[1]){
                    return 1;
                }else if(item1[1] < item2[1]){
                    return -1;
                }else {
                    return 0;
                }
            }else {
                if(item1[0] > item2[0]){
                    return 1;
                }else if(item1[0] < item2[0]){
                    return -1;
                }else {
                    return 0;
                }
            }
        });

        int result = 0;

        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] < intervals[i-1][1]){
                result++;
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
            }
        }

        return result;
    }
}
